package com.leetcode.algorithm.y22.m07;

/**
 * 844. 比较含退格的字符串
 * 
 * https://leetcode.cn/problems/backspace-string-compare/
 * 
 * @author jie.deng
 *
 */
class Question0844Solution01 {

	public boolean backspaceCompare(String s, String t) {
		int lenS = s.length();
		int lenT = t.length();
		int idxS = lenS - 1;
		int idxT = lenT - 1;
		int cntS = 0;
		int cntT = 0;
		while (idxS >= 0 || idxT >= 0) {
			while (idxS >= 0) {
				char chS = s.charAt(idxS);
				if (chS != '#' && cntS == 0) {
					break;
				}
				cntS += (chS == '#' ? 1 : -1);
				idxS--;
			}
			while (idxT >= 0) {
				char chT = t.charAt(idxT);
				if (chT != '#' && cntT == 0) {
					break;
				}
				cntT += (chT == '#' ? 1 : -1);
				idxT--;
			}
			if (idxS >= 0 && idxT >= 0 && t.charAt(idxT) == s.charAt(idxS)) {
				if (t.charAt(idxT) != s.charAt(idxS)) {
					return false;
				}
				idxS--;
				idxT--;
				continue;
			}
			return idxS == -1 && idxT == -1;
		}
		return idxS == -1 && idxT == -1;
	}

}